package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 2021/2/26 下午7:29
 */

class CommonParentTreeNode{

    private HashMap<TreeNode, Map<TreeNode,TreeNode>> cacheMap;

    public CommonParentTreeNode(TreeNode root) {
        cacheMap = new HashMap<>();
        addCache(root);
    }

    public TreeNode findParentTreeNode(TreeNode t1, TreeNode t2) {

        if (t1 == t2) {

            return t1;
        }

        if (t1 == null) {
            return t2;
        }

        if (t2 == null) {
            return t1;
        }

        Map<TreeNode,TreeNode> eachMap = cacheMap.get(t1);
        TreeNode parentNode = eachMap.get(t2);
        if ( eachMap != null &&  parentNode != null) {

            return parentNode;
        }

        eachMap = cacheMap.get(t2);
        parentNode = eachMap.get(t1);

        if (eachMap != null && parentNode != null) {

            return parentNode;
        }
        return null;
    }

    private void addCache(TreeNode node) {

        if (node == null) {
            return;
        }
        // 添加两边的节点
        addBetweenTreeNode(node.left,node);
        addBetweenTreeNode(node.right, node);

        // 两边交叉的
        addContainHead(node.left,node.right, node);

        addCache(node.left);
        addCache(node.right);
    }

    private void addBetweenTreeNode(TreeNode node, TreeNode head) {

        if (node == null) {

            return;
        }

        Map<TreeNode, TreeNode> map = cacheMap.get(node);
        if (map == null) {

            map = new HashMap<>();
            cacheMap.put(node,map);
        }

        map.put(head,head);

        addBetweenTreeNode(node.left,head);
        addBetweenTreeNode(node.right, head);
    }

    private void addContainHead(TreeNode leftNode, TreeNode rightNode, TreeNode head){

        if (leftNode == null) {
            return;
        }

        doAddContainHead(leftNode,rightNode,head);
        addContainHead(leftNode.left,rightNode,head);
        addContainHead(leftNode.right,rightNode,head);
    }

    private void doAddContainHead(TreeNode leftNode,TreeNode rightNode, TreeNode head) {

        if (rightNode == null) {
            return;
        }

        Map<TreeNode, TreeNode> map = cacheMap.get(leftNode);
        if (map == null) {

            map = new HashMap<>();
            cacheMap.put(leftNode,map);
        }

        map.put(rightNode,head);

        doAddContainHead(leftNode,rightNode.left, head);
        doAddContainHead(leftNode,rightNode.right,head);

    }
}

public class _18_查找两个节点的最近公共父节点_cache_all {

    public static void main(String[] args) {
        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.right = new TreeNode(10);

        CommonParentTreeNode parentTreeNode = new CommonParentTreeNode(t1);
        System.out.println(parentTreeNode.findParentTreeNode(t1.left, t1.right.right));
    }
}
